import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Date;

public class Sudoku {

	final static int NB_LIGNE_COL = 9;
	// Permet de savoir les valeurs qui sont par défaut dans le fichier (Donc a
	// ne pas changer)
	public static int[][] sudokuDepart = new int[NB_LIGNE_COL][NB_LIGNE_COL];
	public static int[][] sudoku = new int[NB_LIGNE_COL][NB_LIGNE_COL];
	public static boolean fini = false;

	// Lit le fichier et remplis la grille de sudoku
	public static void lireFichier(String nom) {
		String filePath = nom;
		String retourneLigne = "";
		String line;
		int c;
		int cptLigne = 0;
		int cptColonne = 0;
		try {
			// -------------TEST-------------
			FileReader fichieralire = new FileReader(filePath);
			BufferedReader buff = new BufferedReader(new FileReader(filePath));
			try {
				while ((line = buff.readLine()) != null) {
					for (int i = 0; i < 9; i++) {
						sudoku[cptLigne][cptColonne] = Integer.parseInt(line
								.substring(i, i + 1));
						sudokuDepart[cptLigne][cptColonne] = Integer
								.parseInt(line.substring(i, i + 1));
						cptColonne++;
					}
					cptLigne++;
					cptColonne = 0;
				}
			} finally {
				fichieralire.close();
			}
		} catch (IOException e) {
			System.out.println(e);
		}

	}

	
	public static boolean estValide(int numLigne, int numCol, int valeur) {
		
		//Verif ligne
		for (int i = 0; i < NB_LIGNE_COL; i++) {
			if (sudoku[numLigne][i] == valeur) {
				return false;
			}
		}
		//Verif Col

		for (int i = 0; i < NB_LIGNE_COL; i++) {
			if (sudoku[i][numCol] == valeur) {
				return false;
			}
		}
		
		//Verif carré
		int debutCol = numCol < 3 ? 0 : (numCol < 6) ? 3 : 6;
		// On regarde où commence le carré en fonction de la colonne
		// sélectionnée (0,3 ou 6)
		int debutLigne = numLigne < 3 ? 0 : (numLigne < 6) ? 3 : 6;

		for (int i = debutLigne; i < debutLigne + 3; i++) {
			for (int j = debutCol; j < debutCol + 3; j++) {
				if (sudoku[i][j] == valeur) {
					return false;
				}
			}
		}
		
		return true;
		
	}


	public static void resoudre(int numLigne, int numCol) {

		
		if (numLigne > 8) {
			fini = true;
		}
		
		if (fini) {
			return;
		}
		
		
		// Si la position est déjà rempli (donc différent de 0), on passe au suivant
		if (sudoku[numLigne][numCol] == 0) {
			for (int i = 1; i <= 9; i++) {
				if(fini)
					break;
				
				// Si le chiffre i est nul part on peut l'ajouter et passer à la
				// position suivante sinon on passe au chiffre suivant
				if (estValide(numLigne,numCol, i)) {
					// on ajoute la valeur de i à la grillse
					sudoku[numLigne][numCol] = i;
					// si la colonne est la 8eme , on change de ligne et on
					// remet la colonne à 0 sinon on change juste de colonne
					if (numCol == 8) {
						resoudre(numLigne + 1, 0);
	
					} else {
						resoudre(numLigne, numCol + 1);
					}
				}
			}
		} else {
			if (numCol == 8) {
				resoudre(numLigne + 1, 0);
			} else {
				resoudre(numLigne, numCol + 1);
			}
		}
		
	
		if (fini) {
			return;
		}
		// si aucun numéro ne convient, on remet à 0 la case
		if(sudokuDepart[numLigne][numCol] == 0)
			sudoku[numLigne][numCol] = 0;

	}


	private static void afficherSudoku() {
		for (int i = 0; i < NB_LIGNE_COL; i++) {
			for (int j = 0; j < NB_LIGNE_COL; j++) {
				System.out.print(sudoku[i][j]);
			}
			System.out.println("");
		}

		if(!fini)
			System.out.println("Le sudoku n'a pas de solution");
		else
			System.out.println("Sudoku résolu !");
	}

	public static void main(String[] args) throws Exception {
		lireFichier("sudoku.txt");
		Date date1 = new Date();
		resoudre(0, 0);
		
		System.out.println("Temps exécution (en ms): "+(new Date().getTime() - date1.getTime()));
		
		afficherSudoku();

	}
}